package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicLong;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 98. 验证二叉搜索树
 * @date 2025/1/4 12:35
 */
public class E98 {

    /**
     * <h3>方法一：迭代中序遍历</h3>
     *
     * @param root 根节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode lastPop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode last = stack.peek();
                if (last.right == null) {
                    if (!result.isEmpty() && result.get(result.size() - 1) > last.val)
                        return false;
                    result.add(last.val);
                    lastPop = stack.pop();
                } else if (last.right == lastPop) {
                    lastPop = stack.pop();
                } else {
                    if (!result.isEmpty() && result.get(result.size() - 1) > last.val)
                        return false;
                    result.add(last.val);
                    curr = last.right;
                }
            }
        }
        return true;
    }

    private final List<Integer> result = new ArrayList<>(); // 存储中序遍历的结果

    /**
     * <h3>方法二：递归中序遍历</h3>
     *
     * @param root 根节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST2(root.left);
        if (!result.isEmpty() && result.get(result.size() - 1) >= root.val)
            return false;
        result.add(root.val);
        boolean right = isValidBST2(root.right);
        return left && right;
    }

    private Integer lastVal = null; // 存储前一个节点的值

    /**
     * <h3>方法三：递归中序遍历，更优雅，满老师写的，效率最高</h3>
     *
     * @param root 根节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST3(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST3(root.left)) return false;
        if (lastVal != null && lastVal >= root.val) return false;
        lastVal = root.val;
        return isValidBST3(root.right);
    }

    /**
     * <h3>方法四：递归中序遍历，可变类型</h3>
     *
     * @param root 根节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST4(TreeNode root) {
        return isValidBST4(root, new AtomicLong(Long.MIN_VALUE));
    }

    /**
     * 递归函数
     *
     * @param root 根节点
     * @param prev 上一个节点的值
     * @return 是否是二叉搜索树
     */
    private boolean isValidBST4(TreeNode root, AtomicLong prev) {
        if (root == null) return true;
        if (!isValidBST4(root.left, prev)) return false;
        if (prev.get() >= root.val) return false;
        prev.set(root.val);
        return isValidBST4(root.right, prev);
    }

    /**
     * <h3>方法五：上下界，BST的性质</h3>
     * @param root 根节点
     * @return 是否是二叉搜索树
     */
    public boolean isValidBST5(TreeNode root) {
        return isValidBST5(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 递归函数
     * @param root 根节点
     * @param minValue 最小值
     * @param maxValue 最大值
     * @return 是否是二叉搜索树
     */
    private boolean isValidBST5(TreeNode root, long minValue, long maxValue) {
        if (root == null) return true;
        if (root.val <= minValue || root.val >= maxValue) return false;
        return isValidBST5(root.left, minValue, root.val) && isValidBST5(root.right, root.val, maxValue);
    }
}
